package spann;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
import java.util.Map.Entry;

public class Main {
	public static void main(String[] args) throws Exception { new Main(args); }
	
	//kruskal
	public Main(String[] args) throws Exception {
		
		PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
		HashMap<String, HashSet<String>> minTree = new HashMap<String, HashSet<String>>();
		File f = null;
		if (args.length == 2) {
			f = new File(args[1]);
		} else {
			f = new File("USA-highway-miles.in");
		}
		Scanner scan = new Scanner(f);
		
		while (scan.hasNext()) {
			String line = scan.nextLine();
			if (line.contains("--")) {
				String[] s = line.split("--");
				String c1 = s[0];
				s = s[1].split(" \\[");
				String c2 = s[0];
				int weight = Integer.parseInt(s[1].substring(0, s[1].length()-1));
				
				edges.add(new Edge(c1, c2, weight));
			}
		}
		
		
		int weight=0;
		
		while (!edges.isEmpty()) {
			Edge e = edges.poll();
			if (!cycle(e, minTree)) {
				if (!minTree.containsKey(e.city1)) {
					HashSet<String> h = new HashSet<String>();
					h.add(e.city2);
					minTree.put(e.city1, h);
				} else {
					minTree.get(e.city1).add(e.city2);
				}
				if (!minTree.containsKey(e.city2)) {
					HashSet<String> h = new HashSet<String>();
					h.add(e.city1);
					minTree.put(e.city2, h);
				} else {
					minTree.get(e.city2).add(e.city1);
				}
				
				weight += e.weight;
			}
		}
		
		System.out.println("weight: "+ weight);
		
	}
	
	boolean cycle(Edge e, HashMap<String, HashSet<String>> minTree) {
		if (!minTree.containsKey(e.city1) || !minTree.containsKey(e.city2)) {
			return false;
		}
		HashSet<String> tagged = new HashSet<String>();
		List<String> que = new ArrayList<String>();
		List<String> childQue = new ArrayList<String>();
		
		que.add(e.city2);
		while (!que.isEmpty() || !childQue.isEmpty()) {
			if (que.isEmpty()) {
				que = new ArrayList<String>(childQue);
				childQue.clear();
			}
			if (tagged.contains(que.get(0))) {
				que.remove(0);
				continue;
			}
			tagged.add(que.get(0));
			if (que.get(0).equals(e.city1)) {
				return true;
			}
			childQue.addAll(minTree.get(que.get(0)));
		}
		
		return false;
	}
}

class Edge implements Comparable {
	String city1, city2;
	int weight;
	
	public Edge(String c1, String c2, int w) {
		city1 = c1;
		city2 = c2;
		weight = w;
	}
	
	public String toString() {
		return city1 +" - "+ city2;
	}

	@Override
	public int compareTo(Object arg0) {
		int w = ((Edge)arg0).weight;
		if (w > weight) {
			return -1;
		} else if (w < weight) {
			return 1;
		} else {
			return 0;
		}
	}
}